package com.leetcode.demo;

import java.util.LinkedList;

/**
 * @author 王溪源
 * @ClassName: Question14
 * @Description: 编写一个函数来查找字符串数组中的最长公共前缀
 * @Date 2021/8/22 1:06
 **/
public class Question14 {
    // 构建trie数据结构
    static class TrieNode{
        char content; //装node中的内容
        boolean isEnd; //是否是单词的结尾
        int count;  //这个单词的这个字母下面分支的个数
        LinkedList<TrieNode> childList; //子list


        public TrieNode(){
            childList = new LinkedList<>();
            isEnd = false;
            content = '/';
            count = 0;
        }

        public TrieNode(char c){
            childList = new LinkedList<>();
            isEnd = false;
            content = c;
            count = 0;
        }

        public TrieNode getNode(char content){
            if(childList != null){
                for(TrieNode eachChild : childList){
                    if(eachChild.content == content){
                        return eachChild;
                    }
                }
            }
            return null;
        }

        public void insert(String word){
            TrieNode current = this;
            for (int i = 0; i < word.length (); i++) {
                // 找到当前字符的节点
                TrieNode node = current.getNode (word.charAt (i));
                if(node != null){
                    current = node;
                }else{
                    // 构建插入节点
                    TrieNode trieNode = new TrieNode (word.charAt (i));
                    current.childList.add (trieNode);
                    current = trieNode;
                    //单词下面分支数++
                    current.count++;
                }
            }
            //在单词最后字母那里结束了
            current.isEnd = true;
        }

        public boolean search(String word){
            TrieNode current = this;

            for(int i = 0; i < word.length(); i++){
                if(current.getNode(word.charAt(i)) == null){
                    return false;
                }else{
                    current = current.getNode(word.charAt(i));
                }
            }
            //判断这个单词的这个字母是否在字典里面结束了
            if (current.isEnd == true){
                return true;
            } else{
                return false;
            }
        }

        /**
        * 获取最长公共前缀
        */
        public String getLongestPrefix(){
            StringBuilder sb = new StringBuilder ();
            TrieNode current = this;
            // 只有一个子节点的时候就是公共前缀部分
            while(current.childList != null && current.childList.size () == 1 && !current.isEnd){
                sb.append (current.childList.get (0).content);
                current = current.childList.get (0);
            }
            return sb.toString ();
        }
    }

    public static void main(String[] args) {

        TrieNode trieNode = new TrieNode ();
        trieNode.insert ("ab");
        trieNode.insert ("a");
        //trieNode.insert ("flight");
        System.out.println (trieNode.getLongestPrefix ());
    }
}
